package Offer49;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * 丑数
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 *
 * @author 23737
 * @time 2021.11.10
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().nthUglyNumber(11));
        System.out.println(new Solution().nthUglyNumber2(11));
    }
}

class Solution {
    //过不了的，错误解法，14不是丑数，因为只有一个质因子7
    public int nthUglyNumber(int n) {
        int count = 1;
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            if (checkUglyNumber(i)) {
                count++;
            }
            if (count == n) return i;
        }
        return 0;
    }

    /**
     * 检测一个数是否是丑数
     *
     * @param i 参数
     * @return 布尔值
     */
    private boolean checkUglyNumber(int i) {
        HashSet<Integer> set = new HashSet<>();
        for (int j = 1; j <= i; j++) {
            for (int k = 1; k <= j; k++) {
                if (set.contains(2) || set.contains(3) || set.contains(5)) {
                    System.out.println(i + "--->" + "true");
                    return true;
                }
                if (j * k == i) {
                    set.add(j);
                    set.add(k);
                }
            }
        }
        System.out.println(i + "--->" + "false");
        return false;
    }

    /**
     * 动态规划
     * dp[i] = min(dp[i2]*2,dp[i3]*3,dp[i5]*5)
     * 然后分别比较dp[i]和dp[p2],dp[p3],dp[p5]是否相等,如果相等就将对应的指针加一
     * @param n 参数
     * @return 第n个丑数
     */
    public int nthUglyNumber2(int n) {
        if (n == 0) return 0;
        ArrayList<Integer> array = new ArrayList<Integer>();
        //因为1是丑数，先将1添加进来
        array.add(1);
        int i2 = 0, i3 = 0, i5 = 0;
        while (array.size() < n) {
            int m2 = array.get(i2) * 2;
            int m3 = array.get(i3) * 3;
            int m5 = array.get(i5) * 5;
            //将三个数中的最小值添加进来
            int min = Math.min(m2, Math.min(m3, m5));
            array.add(min);
            if (min == m2) i2++;
            if (min == m3) i3++;
            if (min == m5) i5++;
        }
        return array.get(array.size() - 1);
    }

}
